package cn.edu.xjtu.work.isValidBST;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/**
 * 98. 验证二叉搜索树
 * 
 * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
 * 
 * 假设一个二叉搜索树具有如下特征：
 * 
 * 节点的左子树只包含小于当前节点的数。
 * 
 * 节点的右子树只包含大于当前节点的数。
 * 
 * 所有左子树和右子树自身必须也是二叉搜索树。
 */
public class Solution {

    /**
     * 中序遍历,得到的结果是递增的
     * 
     * @param root
     * @return
     */
    public boolean isValidBST1(TreeNode root) {
        return false;
    }

    /**
     * 构造节点范围区间
     * 
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean valid(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return valid(node.left, lower, node.val) && valid(node.right, node.val, upper);
    }
}
